package Acwing.数学知识;

import java.util.Scanner;

/**
 * @Title: primesWithON
 * @Author 贾金博
 * @Package Acwing.数学知识
 * @Date 2025/4/10 下午10:35
 * @description: O(n)去筛取质数
 */

public class primesWithON {

    private static int[] a;
    private static int[] primes;
    private static int cnt = 0; // 表示质数的个数
    private static boolean[] st; // 表示当前这个数是不是质数
    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n + 10];
        primes = new int[n + 10]; // 里面存取的是 质数 用质数去筛取质数
        st = new boolean[n + 10];

        isPrime();

        System.out.println(cnt);
    }


    public static void isPrime() {
        for(int i = 2; i <= n; i ++ ) {

            if(!st[i]) { // 如果当前这个数 是质数的话 就拿它筛去其他的 合数
                // 先把这个质数给放进来
                primes[ ++ cnt ] = i;
            }

            // 开始更新
            for(int j = 1; primes[j] <= n / i ;j ++ ) {
                st[i * primes[j]] = true;
                if(i % primes[j] == 0) {
                    break;
                }
            }
        }
    }

}
